package dp;

/**
 * 最长重复子数组
 */
public class LongestRepeatSubArr {

    public static void main(String[] args) {
        int[] arr1 = new int[] {1,2,3,2,1};
        int[] arr2 = new int[] {3,2,1,4,5};
        int result = getLongestLengthOfRepeatSubArr(arr1, arr2);
        System.out.println(result);
    }

    private static int getLongestLengthOfRepeatSubArr(int[] arr1,int[] arr2) {
        // dp[i][j]表示 以[0,i]的arr1和[0,j]的arr2的最长重复子数组的长度
        int[][] dp = new int[arr1.length + 1][arr2.length + 1];
        int result = 0;
        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                if (arr1[i-1] == arr2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    result = Math.max(dp[i][j],result);
                }
            }
        }
        Common.print2dArr(dp);
        return result;
    }
}
